'''
对列表进行排序,已知列表中的数范围为(0,100)之间,设计时间复杂发为O(n)的算法
1 3 1 2 1 6 2 4 3
0 0
1 3
2 2
3 2
4 1
6 1
'''


# 必须知道数的范围,有大量的重复元素
def count_sort(li, max_count=100):
    count = [0 for _ in range(max_count + 1)]
    for val in li:
        count[val] += 1
    li.clear()
    for index, val in enumerate(count):
        for i in range(val):
            li.append(index)


import random

li = [random.randint(0, 100) for _ in range(1000)]
print(li)
count_sort(li)
print(li)
